package likouJava;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 课程表 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //1.构建入度表 & 邻接表
        int[] indegree = new int[numCourses];
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] pre : prerequisites){
            int course = pre[0], prereq = pre[1];
            graph.get(prereq).add(course);
            indegree[course]++;
        }

        //2.初始化队列,入度为0的课先入队
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0){
                queue.offer(i);
            }
        }

        //3.拓扑排序
        int count = 0;
        while (!queue.isEmpty()){
            int cur = queue.poll();
            count++;
            for (int next : graph.get(cur)){
                indegree[next]--;
                if (indegree[next] == 0){
                    queue.offer(next);
                }
            }
        }

        //4.判断是否课程学完
        return count == numCourses;
    }


}
